// https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/
// Created by ade on 2022/8/4.
//
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<numeric>

using namespace std;

class Solution {
public:
    vector<int> minSubsequence(vector<int> &nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        sort(nums.rbegin(), nums.rend());
        vector<int> res = {};
        int total = 0;
        int i = 0;
        for (; i < nums.size(); i++) {
            if (total + nums[i] <= sum / 2) {
                total += nums[i];
                res.push_back(nums[i]);
            } else {
                break;
            }
        }
        res.push_back(nums[i]);
        return res;
    }
};

int main() {
    Solution so;
    vector<int> nums = {7, 7, 4};
    auto res = so.minSubsequence(nums);
    for (auto i : res) {
        cout << i << ",";
    }
    return 0;

}